# !/usr/bin/env python
# -*- coding: utf-8 -*-

def insertionSort(arr):
    for i in range(1, len(arr)):
        choose = arr[i]   # 可以认为是选中，要进行插入的牌
        preIndex = i - 1  # 选中的牌的前一个位置（开始进行插入的）
        while preIndex >= 0 and arr[preIndex] > choose:
            # 如果 arr[preIndex] > choose 大于被选中的牌就后移一位
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        # 跳出循环说明找到了一个比手牌小的，插入他的后面
        arr[preIndex+1] = choose
    return arr


if __name__ == '__main__':
    arr = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]
    arr = insertionSort(arr)
    print(arr)